#ifndef _SKIPLIST_H
#define _SKIPLIST_H

#include <cstring>
#include <fstream>
#include <ios>
#include <iostream>
#include <random>
#include <string>
#define STORE_FILE "../store/dumpFile.txt"

namespace raftStoreDataBase
{

    // 定义节点
    template < typename K, typename V >
    class Node
    {
    public:
        Node( K k, V v, int );
        ~Node();
        K get_key() const;
        V get_value() const;
        void set_value( V );
        // 二级指针，就是指针数组，里面存放了不同层级的后一个节点信息，这是用来实现不同和相同层级节点之间的跳转功能。
        Node< K, V > **forward;
        int node_level;  // 这是节点的层级

    private:
        K key;
        V value;
    };

    template < typename K, typename V >
    class SkipList
    {
    public:
        SkipList( int maxLevel );
        ~SkipList();

        int get_random_level();  // 计算插入的这个节点，应该出现在哪一层的索引层。
        Node< K, V > *create_node( K, V, int level );
        int insert_element( K, V );
        void display_list();
        bool search_element( K );
        void delete_element( K );
        void dump_file();
        void load_file();

        // 递归删除元素
        void clear( Node< K, V > * );
        int size();

    private:
        void get_key_value_from_string( const std::string &string, std::string *key, std::string *value );
        bool is_valid_string( const std::string &str );

    private:
        // 需要记录跳表当前元素的个数
        int current_elememt_count_;

        // 文件操作
        std::ofstream file_writer_;
        std::ifstream file_reader_;

        // 跳表的最大层级
        int max_level_;

        // 当前跳表的层级
        int current_skip_list_level_;

        // 跳表的头节点
        Node< K, V > *header_;
    };

    template < typename K, typename V >
    Node< K, V >::Node( const K k, const V v, int level )
    {
        this->key = k;
        this->value = v;
        this->node_level = level;

        this->forward = new Node< K, V > *[ level + 1 ];
        // 这是存放每个层级的后续的下一个节点，比如我这个节点索引层1层2层都有，那么这里存在的就是第1层和第2层的下一个节点。

        memset( this->forward, 0, sizeof( Node< K, V > * ) * ( level + 1 ) );
    }

    template < typename K, typename V >
    Node< K, V >::~Node()
    {
        delete[] forward;
    }

    template < typename K, typename V >
    K Node< K, V >::get_key() const
    {
        return key;
    }

    template < typename K, typename V >
    V Node< K, V >::get_value() const
    {
        return value;
    }

    template < typename K, typename V >
    void Node< K, V >::set_value( V value )
    {
        this->value = value;
    }

    template < typename K, typename V >
    SkipList< K, V >::SkipList( int maxLevel )
        : current_elememt_count_( 0 )
        , max_level_( maxLevel )
        , current_skip_list_level_( 0 )

    {
        // std::cout << "ddd" << std::endl;
        // K k;
        // V v;
        header_ = new Node< K, V >( K(), V(), max_level_ );
    }
    template < typename K, typename V >
    SkipList< K, V >::~SkipList()
    {
        if ( file_writer_.is_open() )
        {
            file_writer_.close();
        }

        if ( file_reader_.is_open() )
        {
            file_reader_.close();
        }
        // 递归删除跳表链条
        if ( header_->forward[ 0 ] != nullptr )
        {
            clear( header_->forward[ 0 ] );
        }
        delete header_;
    }

    template < typename K, typename V >
    void SkipList< K, V >::clear( Node< K, V > *cur )
    {
        if ( cur->forward[ 0 ] != nullptr )
        {
            clear( cur->forward[ 0 ] );
        }
        delete ( cur );
    }

    template < typename K, typename V >
    int SkipList< K, V >::get_random_level()
    {
        // 可以使用random()方法来获取随机过程，但是我选择更加随机的方法
        std::random_device rd;
        std::mt19937 generator( rd() );

        std::uniform_int_distribution<> dist( 1, 2 );
        // 获得随机数
        int level = 0;
        while ( dist( generator ) % 2 )
        {
            level++;
        }

        level = level < max_level_ ? level : max_level_;
        return level;
    }

    template < typename K, typename V >
    Node< K, V > *SkipList< K, V >::create_node( K k, V v, int level )
    {
        Node< K, V > *node = new Node< K, V >( k, v, level );
        if ( !node )
        {
            std::cerr << "创建节点失败" << std::endl;
            return nullptr;
        }
        return node;
    }

    template < typename K, typename V >
    int SkipList< K, V >::insert_element( K key, V value )
    {
        // 首先需要查找元素
        Node< K, V > *current = this->header_;

        // 当插入一个元素时，我们会头节点开始，遍历每层，如果找到了大于当前插入节点的值，就说明我们需要下沉，沉到下一层
        // 但是下层前，我们需要记录这个比我大的值的前一个节点，这样我们才好将这个节点插入当前的索引层。
        Node< K, V > *PreviousNode[ max_level_ + 1 ];
        // 层级是从0开始的
        memset( PreviousNode, 0, sizeof( Node< K, V > * ) * ( max_level_ + 1 ) );

        // 从当前层级开始寻找,这是下沉操作
        for ( int i = current_skip_list_level_; i >= 0; --i )
        {
            // 查找到下一个节点不为空且key大于等于插入节点的
            while ( current->forward[ i ] != nullptr && current->forward[ i ]->get_key() < key )
            {
                current = current->forward[ i ];
            }
            PreviousNode[ i ] = current;
        }

        // 当到达层级0时，将当前节点移动到需要插入的后一个节点中，这样做是为了插入需要插入的节点
        current = current->forward[ 0 ];
        // 判断等于的情况
        if ( current != nullptr && current->get_key() == key )
        {
            std::cerr << "key: " << key << ", exists" << std::endl;
            return 1;
        }

        // 这就是大于的情况了，那么就需要从第0层开始插入元素了
        if ( current == nullptr || current->get_key() > key )
        {

            // 先随机获取到这个节点的层级
            int random_node_level = get_random_level();
            // 如果当前的层级小于random_node_level，则需要新建层级
            if ( random_node_level > current_skip_list_level_ )
            {
                // 还需要在创建顶层索引层
                for ( int i = random_node_level; i > current_skip_list_level_; --i )
                {
                    PreviousNode[ i ] = header_;
                }
                current_skip_list_level_ = random_node_level;
            }

            // 新建节点
            Node< K, V > *insert_node = create_node( key, value, random_node_level );

            // 从第0层开始插入
            for ( int i = 0; i <= random_node_level; ++i )
            {
                // 当前节点的下一个节点链接起来
                insert_node->forward[ i ] = PreviousNode[ i ]->forward[ i ];  // 第i层进行插入
                PreviousNode[ i ]->forward[ i ] = insert_node;
            }

            std::cout << "Successfully inserted key:" << key << ", value:" << value << std::endl;
            current_elememt_count_++;
        }
        return 0;
    }

    template < typename K, typename V >
    void SkipList< K, V >::display_list()
    {
        std::cout << "\n*****Skip List*****" << "\n";
        for ( int i = current_skip_list_level_; i >= 0; --i )
        {
            // 头节点是没有数据的节点，真正有数据的是第一个节点
            Node< K, V > *node = this->header_->forward[ i ];
            while ( node != nullptr )
            {
                std::cout << node->get_key() << ":" << node->get_value() << ";";
                node = node->forward[ i ];
            }
            std::cout << std::endl;
        }
    }

    template < typename K, typename V >
    bool SkipList< K, V >::search_element( K key )
    {
        // 从当前跳表的顶层开始查找
        Node< K, V > *currentNode = this->header_;
        for ( int i = current_skip_list_level_; i >= 0; --i )
        {
            while ( currentNode->forward[ i ] != nullptr && currentNode->forward[ i ]->get_key() < key )
            {
                currentNode = currentNode->forward[ i ];
            }
        }

        // 到这里就是第0层最后一个小于查找值的节点
        currentNode = currentNode->forward[ 0 ];

        if ( currentNode != nullptr && currentNode->get_key() == key )
        {
            std::cout << "Found key: " << key << ", value: " << currentNode->get_value() << std::endl;
            return true;
        }
        std::cout << "Not Found Key:" << key << std::endl;
        return false;
    }

    template < typename K, typename V >
    void SkipList< K, V >::delete_element( K key )
    {
        // 这里和插入节点类似
        // 从顶层开始查找元素
        Node< K, V > *currentNode = this->header_;
        Node< K, V > *PreviousNode[ max_level_ + 1 ];
        // 层级是从0开始的
        memset( PreviousNode, 0, sizeof( Node< K, V > * ) * ( max_level_ + 1 ) );

        // 从顶层开始查找
        for ( int i = current_skip_list_level_; i >= 0; --i )
        {
            while ( currentNode->forward[ i ] != nullptr && currentNode->forward[ i ]->get_key() < key )
            {
                currentNode = currentNode->forward[ i ];
            }
            PreviousNode[ i ] = currentNode;  // 这是存放当前层级找到最后一个小于key的节点 ，i表示层级
        }

        // 运行到这时，currentNode就是第0层的最后一个小于key的节点了，我们就移动到下一个节点
        currentNode = currentNode->forward[ 0 ];
        if ( currentNode != nullptr && currentNode->get_key() == key )
        {
            // 就要从0层开始删除节点
            for ( int i = 0; i <= currentNode->node_level; ++i )
            {
                PreviousNode[ i ]->forward[ i ] = currentNode->forward[ i ];
            }

            // 删除完毕之后，我们需要判断，是否有顶层节点为空情况，我们需要从跳表的当前层级来判断
            while ( current_skip_list_level_ > 0 && header_->forward[ current_skip_list_level_ ] == nullptr )
            {
                current_skip_list_level_--;
            }
            std::cout << "Successfully deleted key " << key << std::endl;
            delete currentNode;
            --current_elememt_count_;
        }
    }

    template < typename K, typename V >
    void SkipList< K, V >::dump_file()
    {
        std::cout << "dump_file-----------------" << std::endl;
        file_writer_.open( STORE_FILE, std::ios::out );
        if ( !file_writer_.is_open() )
        {
            std::cerr << "文件未打开" << std::endl;
            return;
        }
        // 获取到第0层的第一个节点（不包括头节点）
        Node< K, V > *node = this->header_->forward[ 0 ];

        while ( node != nullptr )
        {
            file_writer_ << node->get_key() << ":" << node->get_value();
            std::cout << node->get_key() << ":" << node->get_value() << ";\n";
            node = node->forward[ 0 ];
        }
        // 这里是防止函数运行运行完毕后，还有数据没有写入进去
        file_writer_.flush();
        file_writer_.close();
    }

    template < typename K, typename V >
    void SkipList< K, V >::load_file()
    {
        std::cout << "load_file-----------------" << std::endl;
        file_reader_.open( STORE_FILE, std::ios::in );

        std::string line;
        std::string *key = new std::string();
        std::string *value = new std::string();
        while ( getline( file_reader_, line ) )
        {
            get_key_value_from_string( line, key, value );
            if ( key->empty() || value->empty() )
            {
                continue;
            }
            // Define key as int type
            insert_element( stoi( *key ), *value );
            std::cout << "key:" << *key << "value:" << *value << std::endl;
        }
        delete key;
        delete value;
        file_reader_.close();
    }

    template < typename K, typename V >
    bool SkipList< K, V >::is_valid_string( const std::string &str )
    {

        if ( str.empty() )
        {
            return false;
        }
        if ( str.find( ":" ) == std::string::npos )
        {
            return false;
        }
        return true;
    }

    template < typename K, typename V >
    void SkipList< K, V >::get_key_value_from_string( const std::string &string, std::string *key, std::string *value )
    {
        if ( !is_valid_string( string ) )
        {
            return;
        }

        *key = string.substr( 0, string.find( ":" ) );
        *value = string.substr( string.find( ":" ) + 1 );
    }

    template < typename K, typename V >
    int SkipList< K, V >::size()
    {
        return current_elememt_count_;
    }
}  // namespace raftStoreDataBase

#endif